CS 235 Midterm Topics
=====================

Chapter 5
---------

Logarithms:  Understand the definition of a logarithm in any base, 
know that Log(a*b) = Log(a) + Log(b), know how to apply logarithms 
to basic problems in computer science, such as determining how many 
bits are needed to represent a binary number, or knowing how many times 
a number can be cut in half before the answer is <=1.

Given a code fragment, determine the big-oh running time.

Given an algorithm that takes time t on size n, 
determine the time on size k.

Given an algorithm that takes time t on size n, 
determine the size in time r.

Given a table of empirical results with size and time,
determine the big-oh function that best describes the time.

Given a list of big-oh functions in an arbitrary order,
sort the functions in order of growth.

Given an array of values and an item x to search for,
determine the part of the array in which x could still
be found after each major step of binary search.


Chapter 6
---------

Know what an Iterator is and what its operations do.

Know the behavior of each standard operation for each data type.
list (get, set, add, remove, contains)
stack (push, pop, top)
queue (enqueue, dequeue, getFront)
set (add, remove, contains)
map (get, put, remove, containsKey)
priority queue (insert, findMin, deleteMin)


Chapter 7  
---------

First two fundamental rules of recursion:  base case, make progress.
Examples:  Merge sort, quick sort, Fibonacci

Give running time equation (T(n)) for recursive code


Chapter 8
---------

Determine the content of an array after each major step of insertion
sort.

Determine the content of an array after each major step of selection
sort.

Determine the content of an array in the middle of mergesort after the
two recursive calls to mergesort have completed but before the call to
merge.

Determine the content of an array in the middle of quicksort after the
array has been partitioned but before the two recursive calls to
quicksort.

Know the average case, worst case, and best case big-oh for the following 
algorithms:  selection sort, merge sort, insertion sort, quick sort, 
quick select, binary search